Java8 ArrayDeque 源码解析

前言

今天我们来看看 ArrayDeque，可以说，之前使用的队列的场景不多，所以也没有深入研究队列，但最近在做 LeetCode 的时候，很多时候使用队列会有想不到的功效，比如我们在写 BFS 广度优先遍历的时候，或者在写 二叉树的层次遍历，非递归前序，中序，后序遍历，都会用到这个结构，如果还不会的同学，赶紧去复习一波吧，非常总要，也能为你的笔面试加不少分，很多时候当面试官问道我分析过的源码时，心里那个叫酸爽啊，令面试官刮目相看。闲话不多说了，让我们深入了解一下我们的主角

前世今生

实现了 Deque 接口，Deque 继承了 Queue

public class ArrayDeque<E> extends AbstractCollection<E>
                           implements Deque<E>, Cloneable, Serializable {}

public interface Deque<E> extends Queue<E> {}

Queue

在了解 ArrayDeque 之前，我们先来看看 Queue 有些什么东西，谈到队列，我们会想到先进先出等特性，我把接口贴出来给大家看一下，如果你还不熟悉这几个方法的区别，是该反省一下了！！！一定要熟记，这是基本功

boolean add(E e);

boolean offer(E e);

E remove();

E poll();

E element();

E peek();

Deque

由于是双端队列，多了很多接口，一张图真相，你可能会说，记住这些所有的太难了，太多了，但总结起来，也并不多，在之前的Queue的接口的基础上，加了 First，Last 的接口，是不是一下子变少了

ArrayDeque

终于到了我们的主角了，然而你可能会想，是不是也有LinkedDeque，当初我也这样想过，然而我并没有在 jdk 里找到这个数据结构，但是 LinkedList 却实现了 Deque 也就是说它取代了自己LinkedDeque，也就没有必要多此一举了

属性

既然是 Array，那么里面势必用数组存储，记住，使用 Object[] elements,而不是T[] elements,聪明的你能否想到这样做的目的呢？哈哈。然后是一个head，tail 的指针。

transient Object[] elements; // non-private to simplify nested class access

 /**
  * The index of the element at the head of the deque (which is the
  * element that would be removed by remove() or pop()); or an
  * arbitrary number equal to tail if the deque is empty.
  */
 transient int head;

 /**
  * The index at which the next element would be added to the tail
  * of the deque (via addLast(E), add(E), or push(E)).
  */
 transient int tail;

构造函数

默认开辟了 16 的数组，一般都是这样，预先开辟空间，不够了再扩容。如果自己指定了大小，那么将调用 allocateElements函数，获取一个 2 的幂次方的大小的容量，如果你知道 Hashmap的初始化，那么这个初始化你一定不陌生！至于怎么做到，你可以自己实践一下，这样会理解的更加透彻！

public ArrayDeque() {
    elements = new Object[16];
}
public ArrayDeque(int numElements) {
    allocateElements(numElements);
}
 
public ArrayDeque(Collection<? extends E> c) {
    allocateElements(c.size());
    addAll(c);
}

private void allocateElements(int numElements) {
    elements = new Object[calculateSize(numElements)];
}

private static int calculateSize(int numElements) {
    int initialCapacity = MIN_INITIAL_CAPACITY;
    // Find the best power of two to hold elements.
    // Tests "<=" because arrays aren't kept full.
    if (numElements >= initialCapacity) {
        initialCapacity = numElements;
        initialCapacity |= (initialCapacity >>>  1);
        initialCapacity |= (initialCapacity >>>  2);
        initialCapacity |= (initialCapacity >>>  4);
        initialCapacity |= (initialCapacity >>>  8);
        initialCapacity |= (initialCapacity >>> 16);
        initialCapacity++;

        if (initialCapacity < 0)   // Too many elements, must back off
            initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
    }
    return initialCapacity;
}

普通的方法

add 使用 addLast 在末尾追加元素

public boolean add(E e) {
    addLast(e);
    return true;
}

addLast，直接给数组的末尾元素赋值，之后便是移动tail 指针，这里的扩容实现的很有意思，这也对应了为什么容量要为 2的幂次方，当数组大小刚好为 2 的幂次方时，(tail = (tail + 1) & (elements.length - 1) 为零，也就是说如果head也为0，那么就需要扩容了

public void addLast(E e) {
    if (e == null)
        throw new NullPointerException();
    elements[tail] = e;
    if ( (tail = (tail + 1) & (elements.length - 1)) == head)
        doubleCapacity();
}

doubleCapacity 函数，新数组的大小为两倍，使用 System.arraycopy 函数复制，效率极高。因为 head 不一定为零，所以在扩容的时候，需要恢复head = 0；这里我们应该推测出整个数组都是存储数据，为了方便删除数组而不移动元素，便使用了指针记录状态，这一实现必须要好好琢磨，下次面试别人的时候可以问一下别人，哈哈，有点小坏

private void doubleCapacity() {
    assert head == tail;
    int p = head;
    int n = elements.length;
    int r = n - p; // number of elements to the right of p
    int newCapacity = n << 1;
    if (newCapacity < 0)
        throw new IllegalStateException("Sorry, deque too big");
    Object[] a = new Object[newCapacity];
    System.arraycopy(elements, p, a, 0, r);
    System.arraycopy(elements, 0, a, r, p);
    elements = a;
    head = 0;
    tail = n;
}

pollFirst 获取元素，当然是从 head 位置获取元素，这里需要注意的是，head 如果到了数组末尾，那么又会通过 (h + 1) & (elements.length - 1) 变为 0 了

public E pollFirst() {
    int h = head;
    @SuppressWarnings("unchecked")
    E result = (E) elements[h];
    // Element is null if deque empty
    if (result == null)
        return null;
    elements[h] = null;     // Must null out slot
    head = (h + 1) & (elements.length - 1);
    return result;
}

pollLast 获取队尾元素，如果队尾元素此时为 0，那么将回到了 数组末尾，别问我怎么知道，老师叫你好好学二进制！

public E pollLast() {
    int t = (tail - 1) & (elements.length - 1);
    @SuppressWarnings("unchecked")
    E result = (E) elements[t];
    if (result == null)
        return null;
    elements[t] = null;
    tail = t;
    return result;
}

其他的不涉及到删除，添加到操作就显得尤为简单了，直接获取，就不必多说了

public E getFirst() {
    @SuppressWarnings("unchecked")
    E result = (E) elements[head];
    if (result == null)
        throw new NoSuchElementException();
    return result;
}

/**
 * @throws NoSuchElementException {@inheritDoc}
 */
public E getLast() {
    @SuppressWarnings("unchecked")
    E result = (E) elements[(tail - 1) & (elements.length - 1)];
    if (result == null)
        throw new NoSuchElementException();
    return result;
}

pop 根据先进先出，pop 应该移除队首的元素，注意，这里会抛出异常，如果队首为空的话

 * @throws NoSuchElementException {@inheritDoc}
 */
public E pop() {
    return removeFirst();
}

小结

ArrayDeque 看起来不大，但也有不少东西，知道大概容易，弄懂每一个细节很难，如果你做到了，成功便是你的~